//
// Created by Jason Xu on 2022/10/27.
//

#ifndef THIRDHOMEWORK_BINARYSEARCHTREE_H
#define THIRDHOMEWORK_BINARYSEARCHTREE_H

#include <iostream>
#include <algorithm>
using namespace std;

class tree {
public:
    struct node {
        node *left, *right, *up;
        int val;
        node(node *_left, node *_right, node *_up, int _val) : left{_left}, right{_right}, up{_up}, val{_val} {}
    };

    node *root; ///创建一个根指针

    ///insert一个数字，如果是第一个，就调用newnode创建根，如果是后面的，就调用_insert创建子节点

    node *newnode(int x) { ///输入一个数，创建根，输出根的地址
        node *p = new node{nullptr, nullptr, nullptr, x};
        return p;
    }

    void _insert(node *p, int x) {///输入一个指针和一个数
        //p != nullptr
        if (x <= p->val) {///数小往左走
            if (p->left) _insert(p->left, x); ///如果有节点了，就继续指下去
            else {
                p->left = new node{nullptr, nullptr, p, x};
            }
        } else {///默认不会输入相等的数字，那么数大往右走
            if (p->right) _insert(p->right,x);
            else{
                p->right = new node{nullptr, nullptr, p, x};
            }
        }
    }

    tree () : root{nullptr} {}///构造函数

    void insert(int x)
    {
        if (root == nullptr){
            root = newnode(x);
        }else{
            _insert(root, x);
        }
    }

    void _travel(node *p,int k1, int k2) {//在两点之间实现遍历
        if (p==nullptr) return;
        if (p->val < k1){
            cout<< p -> val << " ";
            _travel(p->right,k1,k2);
        } ///先指到左侧最小值，找到后再往右拐
        if (p->val >= k1 && p->val <= k2 ){
            _travel(p->left,k1,k2);
            cout<< p -> val << " ";
            _travel(p->right,k1,k2);
        }
        if (p->val > k2) {
            _travel(p->left,k1,k2);
            cout<< p -> val << " ";
        }
    }

    void travel(int k1, int k2) {
        _travel(root, k1, k2);
    }

    node* _findMin(node *p){
        if(p->left==nullptr) {
            cout << "Minimum number is "<< p->val <<" ";
            return p;
        }
        else _findMin(p->left);
    }

    void findMin(){
        _findMin(root);
    }

    node* _findMax(node *p){
        if(p->right==nullptr) {
            cout << "Maximum number is "<< p->val <<" ";
            return p;
        }
        else _findMax(p->right);
    }

    void findMax(){
        _findMax(root);
    }

/*
    void _remove(node *p, int x){
        if(p==nullptr) return;
        if(p->val==x)//如果删除根节点{
            //不太会写代码，大体意思是：如果有左子，1.让左子最大值补位，如果没有，2.让右子最小值补位，3.如果都没有,删自己
            if(p->left!= nullptr){
                p->left=_findMax(p->left);
                return;
        }
        else //如果不是删除根节点

    }
    void remove(int x){
        _remove(root, x);
    }
 */

};




#endif //THIRDHOMEWORK_BINARYSEARCHTREE_H